#include <iostream> 
#include <vector>
using namespace std;

bool dfs(vector<vector<char>>& grid,vector<vector<bool>>& visit,vector<vector<bool>>& path,int pi,int pj,int i,int j,int w,int h){
	visit[i][j] = true;
	path[i][j] = true;
	char c = grid[i][j];
	
	if( i-1>=0 && !visit[i-1][j] && grid[i-1][j]==c) if( dfs(grid,visit,path,i,j,i-1,j,w,h) ) {path[i][j] = false; return true;}
	if( i+1<h && !visit[i+1][j] && grid[i+1][j]==c ) if( dfs(grid,visit,path,i,j,i+1,j,w,h) ) {path[i][j] = false; return true;}
	if( j-1>=0 && !visit[i][j-1] && grid[i][j-1]==c) if( dfs(grid,visit,path,i,j,i,j-1,w,h) ){path[i][j] = false; return true;}
	if( j+1<w && !visit[i][j+1] && grid[i][j+1]==c) if( dfs(grid,visit,path,i,j,i,j+1,w,h) ) {path[i][j] = false; return true;}
	path[i][j] = false;
	if( i-1>=0 && c==grid[i-1][j] && path[i-1][j] &&pi!=i-1) return true;
	else if( i+1<h && c==grid[i+1][j] && path[i+1][j] &&pi!=i+1) return true;
	else if( j-1>=0 && c==grid[i][j-1] && path[i][j-1] &&pj!=j-1) return true;
	else if( j+1<w && c==grid[i][j+1] && path[i][j+1] &&pj!=j+1) return true;
	else return false;
}
bool containsCycle(vector<vector<char>>& grid) {

	int w = grid[0].size(),h = grid.size();
		vector<vector<bool>> visit = *new vector<vector<bool>>(h);
	vector<vector<bool>> path = *new vector<vector<bool>>(h);
	for(int i=0;i<grid.size(); i++ ) visit[i] = *new vector<bool>(grid[0].size(),false);
	for(int i=0;i<grid.size(); i++ ) path[i] = *new vector<bool>(grid[0].size(),false);
    for(int i=0; i<grid.size(); i++){
        for(int j=0; j<grid[i].size(); j++){
        	cout << i<<" " << j << endl;
            if( !visit[i][j] ){
            	path[i][j] = true;
			
	            visit[i][j] = true;
	            char c = grid[i][j];
	        	if( i-1>=0 && !visit[i-1][j] && grid[i-1][j]==c) if( dfs(grid,visit,path,i,j,i-1,j,w,h) ) return true;
				if( i+1<h && !visit[i+1][j] && grid[i+1][j]==c ) if( dfs(grid,visit,path,i,j,i+1,j,w,h) ) return true;
				if( j-1>=0 && !visit[i][j-1] && grid[i][j-1]==c) if( dfs(grid,visit,path,i,j,i,j-1,w,h) ) return true;
				if( j+1<w && !visit[i][j+1] && grid[i][j+1]==c) if( dfs(grid,visit,path,i,j,i,j+1,w,h) ) return true;
	            cout << visit.size() << endl;
	            path[i][j] = false;
      		}
        }            
    }
    return false;
}
int main(){
	vector<vector<char>> v = {{'a','a','a','a'},{'a','b','c','d'},{'a','b','b','a'},{'a','a','a','a'}};
	vector<vector<char>> v1 = {{'c','c','c','a'},{'c','d','c','c'},{'c','c','e','c'},{'f','c','c','c'}};
	cout << containsCycle(v);
	return 0;
}
